home *** CD-ROM | disk | FTP | other *** search
/ Shareware Super Platinum 8 / Shareware Super Platinum 8.iso / mac / WIN_PRO / DS-1.ZIP;1 / RUNTIME.ZIP / RLRGINT.R < prev    next >
Encoding:
Text File  |  1992-02-10  |  47.7 KB  |  2,007 lines
  1. /*
  2.  * File: rlrgint.r
  3.  *  Large integer arithmetic
  4.  */
  5.  
  6. #ifdef LargeInts
  7.  
  8. extern int over_flow;
  9.  
  10. /*
  11.  *  Conventions:
  12.  *
  13.  *  Lrgints entering this module and leaving it are too large to
  14.  *  be represented with T_Integer.  So, externally, a given value
  15.  *  is always T_Integer or always T_Lrgint.
  16.  *
  17.  *  Routines outside this module operate on bignums by calling
  18.  *  a routine like
  19.  *
  20.  *      bigadd(da, db, dx)
  21.  *
  22.  *  where da, db, and dx are pointers to tended descriptors.
  23.  *  For the common case where one argument is a T_Integer, these
  24.  *  call routines like
  25.  *
  26.  *      bigaddi(da, IntVal(*db), dx).
  27.  *
  28.  *  The bigxxxi routines can convert an integer to bignum form;
  29.  *  they use itobig.
  30.  *
  31.  *  The routines that actually do the work take (length, address)
  32.  *  pairs specifying unsigned base-B digit strings.  The sign handling
  33.  *  is done in the bigxxx routines.
  34.  */
  35.  
  36. /*
  37.  * Type for doing arithmetic on (2 * NB)-bit nonnegative numbers.
  38.  *  Normally unsigned but may be signed (with NB reduced appropriately)
  39.  *  if unsigned arithmetic is slow.
  40.  */
  41.  
  42. /* The bignum radix, B */
  43.  
  44. #define B            ((word)1 << NB)
  45.  
  46. /* Lrgint digits in a word */
  47.  
  48. #define WORDLEN  (WordBits / NB + (WordBits % NB != 0))
  49.  
  50. /* size of a bignum block that will hold an integer */
  51.  
  52. #define INTBIGBLK  sizeof(struct b_bignum) + sizeof(DIGIT) * WORDLEN
  53.  
  54. /* lo(uword d) :            the low digit of a uword
  55.    hi(uword d) :            the rest, d is unsigned
  56.    signed_hi(uword d) :     the rest, d is signed
  57.    dbl(DIGIT a, DIGIT b) : the two-digit uword [a,b] */
  58.  
  59. #define lo(d)        ((d) & (B - 1))
  60. #define hi(d)        ((uword)(d) >> NB)
  61. #define dbl(a,b)     (((uword)(a) << NB) + (b))
  62.  
  63. #if ((-1) >> 1) < 0
  64. #define signed_hi(d) ((word)(d) >> NB)
  65. #else
  66. #define signbit      ((uword)1 << (WordBits - NB - 1))
  67. #define signed_hi(d) ((word)((((uword)(d) >> NB) ^ signbit) - signbit))
  68. #endif
  69.  
  70. /* LrgInt(dptr dp) : the struct b_bignum pointed to by dp */
  71.  
  72. #define LrgInt(dp)   ((struct b_bignum *)&BlkLoc(*dp)->bignumblk)
  73.  
  74. /* LEN(struct b_bignum *b) : number of significant digits */
  75.  
  76. #define LEN(b)       ((b)->lsd - (b)->msd + 1)
  77.  
  78. /* DIG(struct b_bignum *b, word i): pointer to ith most significant digit */
  79.  
  80. #define DIG(b,i)     (&(b)->digits[(b)->msd+(i)])
  81.  
  82. /* ceil, ln: ceil may be 1 too high in case ln is inaccurate */
  83.  
  84. #undef ceil
  85. #define ceil(x)      ((word)((x) + 1.01))
  86. #define ln(n)        (log((double)n))
  87.  
  88. /* determine the number of words needed for a bignum block with n digits */
  89.  
  90. #define LrgNeed(n)   ( ((sizeof(struct b_bignum) + ((n) - 1) * sizeof(DIGIT)) \
  91.                + WordSize - 1) & -WordSize )
  92.  
  93. /* copied from rconv.c */
  94.  
  95. #if !EBCDIC
  96. #define tonum(c)     (isdigit(c) ? (c)-'0' : 10+(((c)|(040))-'a'))
  97. #endif                    /* !EBCDIC */
  98.  
  99. /* copied from oref.c */
  100.  
  101. #define RandVal (RanScale*(k_random=(RandA*(long)k_random+RandC)&0x7fffffffL))
  102.  
  103. /*
  104.  * Prototypes.
  105.  */
  106.  
  107. hidden int mkdesc    Params((struct b_bignum *x, dptr dx));
  108. hidden novalue itobig    Params((word i, struct b_bignum *x, dptr dx));
  109.  
  110. hidden novalue decout    Params((FILE *f, DIGIT *n, word l));
  111.  
  112. hidden int bigaddi    Params((dptr da, word i, dptr dx));
  113. hidden int bigsubi    Params((dptr da, word i, dptr dx));
  114. hidden int bigmuli    Params((dptr da, word i, dptr dx));
  115. hidden int bigdivi    Params((dptr da, word i, dptr dx));
  116. hidden int bigmodi    Params((dptr da, word i, dptr dx));
  117. hidden int bigpowi    Params((dptr da, word i, dptr dx));
  118. hidden int bigpowii    Params((word a, word i, dptr dx));
  119. hidden word bigcmpi    Params((dptr da, word i));
  120.  
  121. hidden DIGIT add1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  122. hidden word sub1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  123. hidden novalue mul1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n, word m));
  124. hidden int div1    
  125.         Params((DIGIT *a, DIGIT *b, DIGIT *q, DIGIT *r, word m, word n));
  126. hidden novalue compl1    Params((DIGIT *u, DIGIT *w, word n));
  127. hidden word cmp1    Params((DIGIT *u, DIGIT *v, word n));
  128. hidden DIGIT addi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  129. hidden novalue subi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  130. hidden DIGIT muli1    Params((DIGIT *u, word k, int c, DIGIT *w, word n));
  131. hidden DIGIT divi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  132. hidden DIGIT shifti1    Params((DIGIT *u, word k, DIGIT c, DIGIT *w, word n));
  133. hidden word cmpi1    Params((DIGIT *u, word k, word n));
  134.  
  135. #ifdef SysMem
  136. #define bdzero(dest,l)  memset(dest, '\0', (l) * sizeof(DIGIT))
  137. #define bdcopy(src, dest, l)  memcpy(dest, src, (l) * sizeof(DIGIT))
  138. #else                    /* SysMem */
  139. hidden novalue bdzero   Params((DIGIT *dest, word l));
  140. hidden novalue bdcopy   Params((DIGIT *src, DIGIT *dest, word l));
  141. #endif                    /* SysMem */
  142.  
  143. /*
  144.  * mkdesc -- put value into a descriptor
  145.  */
  146.  
  147. static int mkdesc(x, dx)
  148. struct b_bignum *x;
  149. dptr dx;
  150. {
  151.    word xlen, cmp;
  152.    static DIGIT maxword[WORDLEN] = { 1 << ((WordBits - 1) % NB) };
  153.  
  154.    /* suppress leading zero digits */
  155.  
  156.    while (x->msd != x->lsd && *DIG(x,0) == 0)
  157.       x->msd++;
  158.  
  159.    /* put it into a word if it fits, otherwise return the bignum */
  160.  
  161.    xlen = LEN(x);
  162.  
  163.    if (xlen < WORDLEN ||
  164.        (xlen == WORDLEN && ((cmp = cmp1(DIG(x,0), maxword, (word)WORDLEN)) < 0 ||
  165.         (cmp == (word)0 && x->sign)))) {
  166.       word val = -(word)*DIG(x,0);
  167.       word i;
  168.  
  169.       for (i = x->msd; ++i <= x->lsd; )
  170.          val = (val << NB) - x->digits[i];
  171.       if (!x->sign)
  172.      val = -val;
  173.       dx->dword = D_Integer;
  174.       IntVal(*dx) = val;
  175.       }
  176.    else {
  177.       dx->dword = D_Lrgint;
  178.       BlkLoc(*dx) = (union block *)x;
  179.       }
  180.    return Succeeded;
  181. }
  182.  
  183. /*
  184.  *  i -> big
  185.  */
  186.  
  187. static novalue itobig(i, x, dx)
  188. word i;
  189. struct b_bignum *x;
  190. dptr dx;
  191. {
  192.    x->lsd = WORDLEN - 1;
  193.    x->msd = WORDLEN;
  194.    x->sign = 0;
  195.  
  196.    if (i == 0) {
  197.       x->msd--;
  198.       *DIG(x,0) = 0;
  199.       }
  200.    else if (i < 0) {
  201.       word d = lo(i);
  202.  
  203.       if (d != 0) {
  204.          d = B - d;
  205.          i += B;
  206.          }
  207.       i = - signed_hi(i);
  208.       x->msd--;
  209.       *DIG(x,0) = d;
  210.       x->sign = 1;
  211.       }
  212.             
  213.    while (i != 0) {
  214.       x->msd--;
  215.       *DIG(x,0) = lo(i);
  216.       i = hi(i);
  217.       }
  218.  
  219.    dx->dword = D_Lrgint;
  220.    BlkLoc(*dx) = (union block *)x;
  221. }
  222.  
  223. /*
  224.  *  string -> bignum 
  225.  */
  226.  
  227. word bigradix(sign, r, s, end_s, result)
  228. int sign;                      /* '-' or not */
  229. int r;                          /* radix 2 .. 36 */
  230. char *s, *end_s;                        /* input string */
  231. union numeric *result;          /* output T_Integer or T_Lrgint */
  232. {
  233.    struct b_bignum *b;
  234.    DIGIT *bd;
  235.    word len;
  236.    int c;
  237.  
  238.    if (r == 0)
  239.       return CvtFail;
  240.    len = ceil((end_s - s) * ln(r) / ln(B));
  241.    b = alcbignum(len);
  242.    if (b == NULL)
  243.       return Error;
  244.    bd = DIG(b,0);
  245.  
  246.    bdzero(bd, len);
  247.  
  248.    if (r < 2 || r > 36)
  249.       return CvtFail;
  250.  
  251.    for (c = ((s < end_s) ? *s++ : ' '); isalnum(c);
  252.         c = ((s < end_s) ? *s++ : ' ')) {
  253.       c = tonum(c);
  254.       if (c >= r)
  255.      return CvtFail;
  256.       muli1(bd, (word)r, c, bd, len);
  257.       }
  258.  
  259.    /*
  260.     * Skip trailing white space and make sure there is nothing else left
  261.     *  in the string. Note, if we have already reached end-of-string,
  262.     *  c has been set to a space.
  263.     */
  264.    while (isspace(c) && s < end_s)
  265.       c = *s++;
  266.    if (!isspace(c))
  267.       return CvtFail;
  268.  
  269.    if (sign == '-')
  270.       b->sign = 1;
  271.  
  272.    /* put value into dx and return the type */
  273.  
  274.    { struct descrip dx;
  275.    (void)mkdesc(b, &dx);
  276.    if (Type(dx) == T_Lrgint)
  277.      result->big = (struct b_bignum *)BlkLoc(dx);
  278.    else
  279.      result->integer = IntVal(dx);
  280.    return Type(dx);
  281.    }
  282. }
  283.  
  284. /*
  285.  *  bignum -> real
  286.  */
  287.  
  288. double bigtoreal(da)
  289. dptr da;
  290. {
  291.    word i;
  292.    double r = 0;
  293.    struct b_bignum *b = &BlkLoc(*da)->bignumblk;
  294.  
  295.    for (i = b->msd; i <= b->lsd; i++)
  296.       r = r * B + b->digits[i];
  297.  
  298.    return (b->sign ? -r : r);
  299. }
  300.  
  301. /*
  302.  *  real -> bignum
  303.  */
  304.  
  305. int realtobig(da, dx)
  306. dptr da, dx;
  307. {
  308.  
  309. #ifdef Double
  310.    double x;
  311. #else                    /* Double */
  312.    double x = BlkLoc(*da)->realblk.realval;
  313. #endif                    /* Double */
  314.  
  315.    struct b_bignum *b;
  316.    word i, blen;
  317.    word d;
  318.  
  319. #ifdef Double
  320.     {
  321.         int    *rp, *rq;
  322.         rp = (word *) &(BlkLoc(*da)->realblk.realval);
  323.         rq = (word *) &x;
  324.         *rq++ = *rp++;
  325.         *rq = *rp;
  326.     }
  327. #endif                    /* Double */
  328.  
  329.    if (x > 0.9999 * MinLong && x < 0.9999 * MaxLong) {
  330.       MakeInt((word)x, dx);
  331.       return Succeeded;        /* got lucky; a simple integer suffices */
  332.       }
  333.  
  334.    x = x > 0 ? x : -x;
  335.    blen = ln(x) / ln(B) + 0.99;
  336.    for (i = 0; i < blen; i++)
  337.       x /= B;
  338.    if (x >= 1.0) {
  339.       x /= B;
  340.       blen += 1;
  341.       }
  342.  
  343.    Protect(b = alcbignum(blen), return Error);
  344.    for (i = 0; i < blen; i++) {
  345.       d = (x *= B);
  346.       *DIG(b,i) = d;
  347.       x -= d;
  348.       }
  349.      
  350.    b->sign = x < 0;
  351.    return mkdesc(b, dx);
  352. }
  353.  
  354. /*
  355.  *  bignum -> string
  356.  */
  357.  
  358. int bigtos(da, dx)
  359. dptr da, dx;
  360. {
  361.    struct b_bignum *a, *temp;
  362.    word alen = LEN(LrgInt(da));
  363.    word slen = ceil(alen * ln(B) / ln(10));
  364.    char *p, *q;
  365.  
  366.    a = LrgInt(da);
  367.    Protect(temp = alcbignum(alen), fatalerr(0,NULL));
  368.    if (a->sign)
  369.       slen++;
  370.    Protect(q = alcstr(NULL,slen), fatalerr(0,NULL));
  371.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  372.    p = q += slen;
  373.    while (cmpi1(DIG(temp,0), (word)0, alen))
  374.       *--p = '0' + divi1(DIG(temp,0), (word)10, DIG(temp,0), alen);
  375.    if (a->sign)
  376.       *--p = '-';
  377.    StrLen(*dx) = q - p;
  378.    StrLoc(*dx) = p;
  379.    return NoCvt;    /* The mnemonic is wrong, but the signal means */
  380.             /* that the string is allocated and not null- */
  381.             /* terminated. */
  382. }
  383.  
  384. /*
  385.  *  bignum -> file 
  386.  */
  387.  
  388. novalue bigprint(f, da)
  389. FILE *f;
  390. dptr da;
  391. {
  392.    struct b_bignum *a, *temp;
  393.    word alen = LEN(LrgInt(da));
  394.    word slen, dlen;
  395.  
  396.    slen = (BlkLoc(*da)->bignumblk.lsd - BlkLoc(*da)->bignumblk.msd + 1);
  397.    dlen = slen * NB * 0.3010299956639812;    /* 1 / log2(10) */
  398.    if (dlen > MaxDigits) {
  399.       fprintf(f, "integer(~%ld)",dlen - 2);    /* center estimate */
  400.       return;
  401.       }
  402.  
  403.    /* not worth passing this one back */
  404.    Protect(temp = alcbignum(alen), fatalerr(0, NULL));
  405.  
  406.    a = LrgInt(da);
  407.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  408.    if (a->sign)
  409.       putc('-', f);
  410.    decout(f, DIG(temp,0), alen);
  411. }
  412.  
  413. /*
  414.  * decout - given a base B digit string, print the number in base 10.
  415.  */
  416. static novalue decout(f, n, l)
  417. FILE *f;
  418. DIGIT *n;
  419. word l;
  420. {
  421.    DIGIT i = divi1(n, (word)10, n, l);
  422.  
  423.    if (cmpi1(n, (word)0, l))
  424.       decout(f, n, l);
  425.    putc('0' + i, f);
  426. }
  427.  
  428. /*
  429.  *  da -> dx
  430.  */
  431.  
  432. int cpbignum(da, dx)
  433. dptr da, dx;
  434. {
  435.    struct b_bignum *a;
  436.    word alen = LEN(LrgInt(da));
  437.    struct b_bignum *x;
  438.  
  439.    Protect(x = alcbignum(alen), return Error);
  440.    a = LrgInt(da);
  441.    bdcopy(DIG(a,0), DIG(x,0), alen);
  442.    x->sign = a->sign;
  443.    return mkdesc(x, dx);
  444. }
  445.  
  446. /*
  447.  *  da + db -> dx
  448.  */
  449.  
  450. int bigadd(da, db, dx)
  451. dptr da, db;
  452. dptr dx;
  453. {
  454.    struct b_bignum *x, *a, *b;
  455.    word alen, blen;
  456.    word c;
  457.  
  458.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  459.       alen = LEN(LrgInt(da));
  460.       blen = LEN(LrgInt(db));
  461.       a = LrgInt(da);
  462.       b = LrgInt(db);
  463.       if (a->sign == b->sign) {
  464.          if (alen > blen) {
  465.             Protect(x = alcbignum(alen + 1), return Error);
  466.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  467.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  468.             }
  469.          else if (alen == blen) {
  470.             Protect(x = alcbignum(alen + 1), return Error);
  471.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  472.             }
  473.          else {
  474.             Protect(x = alcbignum(blen + 1), return Error);
  475.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  476.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  477.             }
  478.          x->sign = a->sign;
  479.          }
  480.       else {
  481.          if (alen > blen) {
  482.             Protect(x = alcbignum(alen), return Error);
  483.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  484.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  485.             x->sign = a->sign;
  486.             }
  487.          else if (alen == blen) {
  488.             Protect(x = alcbignum(alen), return Error);
  489.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  490.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  491.                x->sign = a->sign;
  492.                }
  493.             else {
  494.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  495.                x->sign = b->sign;
  496.                }
  497.             }
  498.          else {
  499.             Protect(x = alcbignum(blen), return Error);
  500.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  501.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  502.             x->sign = b->sign;
  503.             }
  504.          }
  505.       return mkdesc(x, dx);
  506.       }
  507.    else if (Type(*da) == T_Lrgint)    /* bignum + integer */
  508.       return bigaddi(da, IntVal(*db), dx);
  509.    else if (Type(*db) == T_Lrgint)    /* integer + bignum */
  510.       return bigaddi(db, IntVal(*da), dx);
  511.    else {                             /* integer + integer */
  512.       struct descrip td;
  513.       char tdigits[INTBIGBLK];
  514.  
  515.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  516.       return bigaddi(&td, IntVal(*db), dx);
  517.       }
  518. }
  519.  
  520. /*
  521.  *  da - db -> dx
  522.  */ 
  523.  
  524. int bigsub(da, db, dx)
  525. dptr da, db, dx;
  526. {
  527.    struct descrip td;
  528.    char tdigits[INTBIGBLK];
  529.    struct b_bignum *a, *b, *x;
  530.    word alen, blen;
  531.    word c;
  532.  
  533.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  534.       alen = LEN(LrgInt(da));
  535.       blen = LEN(LrgInt(db));
  536.       a = LrgInt(da);
  537.       b = LrgInt(db);
  538.       if (a->sign != b->sign) {
  539.          if (alen > blen) {
  540.             Protect(x = alcbignum(alen + 1), return Error);
  541.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  542.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  543.             }
  544.          else if (alen == blen) {
  545.             Protect(x = alcbignum(alen + 1), return Error);
  546.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  547.             }
  548.          else {
  549.             Protect(x = alcbignum(blen + 1), return Error);
  550.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  551.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  552.             }
  553.          x->sign = a->sign;
  554.          }
  555.       else {
  556.          if (alen > blen) {
  557.             Protect(x = alcbignum(alen), return Error);
  558.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  559.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  560.             x->sign = a->sign;
  561.             }
  562.          else if (alen == blen) {
  563.             Protect(x = alcbignum(alen), return Error);
  564.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  565.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  566.                x->sign = a->sign;
  567.                }
  568.             else {
  569.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  570.                x->sign = 1 ^ b->sign;
  571.                }
  572.             }
  573.          else {
  574.             Protect(x = alcbignum(blen), return Error);
  575.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  576.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  577.             x->sign = 1 ^ b->sign;
  578.             }
  579.          }
  580.       return mkdesc(x, dx);
  581.       }
  582.    else if (Type(*da) == T_Lrgint)     /* bignum - integer */
  583.       return bigsubi(da, IntVal(*db), dx);
  584.    else if (Type(*db) == T_Lrgint) {   /* integer - bignum */
  585.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  586.       alen = LEN(LrgInt(&td));
  587.       blen = LEN(LrgInt(db));
  588.       a = LrgInt(&td);
  589.       b = LrgInt(db);
  590.       if (a->sign != b->sign) {
  591.          if (alen == blen) {
  592.             Protect(x = alcbignum(alen + 1), return Error);
  593.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  594.             }
  595.          else {
  596.             Protect(x = alcbignum(blen + 1), return Error);
  597.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  598.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  599.             }
  600.          x->sign = a->sign;
  601.          }
  602.       else {
  603.          if (alen == blen) {
  604.             Protect(x = alcbignum(alen), return Error);
  605.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  606.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  607.                x->sign = a->sign;
  608.                }
  609.             else {
  610.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  611.                x->sign = 1 ^ b->sign;
  612.                }
  613.             }
  614.          else {
  615.             Protect(x = alcbignum(blen), return Error);
  616.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  617.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  618.             x->sign = 1 ^ b->sign;
  619.             }
  620.          }
  621.       return mkdesc(x, dx);
  622.       }
  623.    else {                              /* integer - integer */
  624.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  625.       return bigsubi(&td, IntVal(*db), dx);
  626.       }
  627.       
  628. }
  629.  
  630. /*
  631.  *  da * db -> dx
  632.  */
  633.  
  634. int bigmul(da, db, dx)
  635. dptr da, db, dx;
  636. {
  637.    struct b_bignum *a, *b, *x;
  638.    word alen, blen;
  639.  
  640.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  641.       alen = LEN(LrgInt(da));
  642.       blen = LEN(LrgInt(db));
  643.       a = LrgInt(da);
  644.       b = LrgInt(db);
  645.       Protect(x = alcbignum(alen + blen), return Error);
  646.       mul1(DIG(a,0), DIG(b,0), DIG(x,0), alen, blen);
  647.       x->sign = a->sign ^ b->sign;
  648.       return mkdesc(x, dx);
  649.       }
  650.    else if (Type(*da) == T_Lrgint)    /* bignum * integer */
  651.       return bigmuli(da, IntVal(*db), dx);
  652.    else if (Type(*db) == T_Lrgint)    /* integer * bignum */
  653.       return bigmuli(db, IntVal(*da), dx);
  654.    else {                             /* integer * integer */
  655.       struct descrip td;
  656.       char tdigits[INTBIGBLK];
  657.  
  658.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  659.       return bigmuli(&td, IntVal(*db), dx);
  660.       }
  661. }
  662.  
  663. /*
  664.  *  da / db -> dx
  665.  */
  666.  
  667. int bigdiv(da, db, dx)
  668. dptr da, db, dx;
  669. {
  670.    struct b_bignum *a, *b, *x;
  671.    word alen, blen;
  672.  
  673.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  674.       alen = LEN(LrgInt(da));
  675.       blen = LEN(LrgInt(db));
  676.       if (alen < blen) {
  677.          MakeInt(0, dx);
  678.          return Succeeded;
  679.          }
  680.       a = LrgInt(da);
  681.       b = LrgInt(db);
  682.       Protect(x = alcbignum(alen - blen + 1), return Error);
  683.       if (blen == 1)
  684.          divi1(DIG(a,0), (word)*DIG(b,0), DIG(x,0), alen);
  685.       else {
  686.          if (div1(DIG(a,0), DIG(b,0), DIG(x,0), NULL, alen-blen, blen) == Error)
  687.             return Error;
  688.             }
  689.       x->sign = a->sign ^ b->sign;
  690.       return mkdesc(x, dx);
  691.       }
  692.    else if (Type(*da) == T_Lrgint)     /* bignum / integer */
  693.       return bigdivi(da, IntVal(*db), dx);
  694.    else if (Type(*db) == T_Lrgint) {   /* integer / bignum */
  695.       MakeInt(0, dx);
  696.       return Succeeded;
  697.       }
  698.    /* not called for integer / integer */
  699. }
  700.  
  701. /*
  702.  *  da % db -> dx
  703.  */
  704.  
  705. int bigmod(da, db, dx)
  706. dptr da, db, dx;
  707. {
  708.    struct b_bignum *a, *b, *x, *temp;
  709.    word alen, blen;
  710.  
  711.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  712.       alen = LEN(LrgInt(da));
  713.       blen = LEN(LrgInt(db));
  714.       if (alen < blen) {
  715.          cpbignum(da, dx);
  716.          return Succeeded;
  717.          }
  718.       a = LrgInt(da);
  719.       b = LrgInt(db);
  720.       Protect(x = alcbignum(blen), return Error);
  721.       if (blen == 1) {
  722.      Protect(temp = alcbignum(alen), return Error);
  723.          *DIG(x,0) = divi1(DIG(a,0), (word)*DIG(b,0), DIG(temp,0), alen);
  724.          }
  725.       else {
  726.          if (div1(DIG(a,0), DIG(b,0), NULL, DIG(x,0), alen-blen, blen) == Error)
  727.             return Error;
  728.             }
  729.       x->sign = a->sign;
  730.       return mkdesc(x, dx);
  731.       }
  732.    else if (Type(*da) == T_Lrgint)     /* bignum % integer */
  733.       return bigmodi(da, IntVal(*db), dx);
  734.    else if (Type(*db) == T_Lrgint) {   /* integer % bignum */
  735.       struct descrip td;
  736.       char tdigits[INTBIGBLK];
  737.  
  738.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  739.       cpbignum(&td, dx);
  740.       return Succeeded;
  741.       }
  742.    /* not called for integer % integer */
  743. }
  744.  
  745. /*
  746.  *  -i -> dx
  747.  */
  748.  
  749. int bigneg(da, dx)
  750. dptr da, dx;
  751. {
  752.    struct descrip td;
  753.    char tdigits[INTBIGBLK];
  754.  
  755.    itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  756.    LrgInt(&td)->sign ^= 1;
  757.    return cpbignum(&td, dx);
  758. }
  759.  
  760. /*
  761.  *  da ^ db -> dx
  762.  */
  763.  
  764. int bigpow(da, db, dx)
  765. dptr da, db, dx;
  766. {
  767.    word n;
  768.  
  769.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  770.       if (LrgInt(db)->sign) {
  771.          MakeInt(0, dx);
  772.          }
  773.       else {
  774.          n = LEN(LrgInt(db)) * NB;
  775.          /* scan bits left to right.  skip leading 1. */
  776.          while (--n >= 0)
  777.             if ((*DIG(LrgInt(db), n / NB) & (1 << (n % NB))))
  778.                break;
  779.          /* then, for each zero, square the partial result;
  780.           *  for each one, square it and multiply it by a */
  781.          *dx = *da;
  782.          while (--n >= 0) {
  783.             if (bigmul(dx, dx, dx) == Error)
  784.            return Error;
  785.             if ((*DIG(LrgInt(db), n / NB) & (1 << (n % NB))))
  786.                if (bigmul(dx, da, dx) == Error)
  787.           return Error;
  788.         }
  789.          }
  790.       return Succeeded;
  791.       }
  792.    else if (Type(*da) == T_Lrgint)    /* bignum ^ integer */
  793.       return bigpowi(da, IntVal(*db), dx);
  794.    else if (Type(*db) == T_Lrgint)    /* integer ^ bignum */
  795.       return bigpowii(IntVal(*da), (word)bigtoreal(db), dx);
  796.    else                               /* integer ^ integer */
  797.       return bigpowii(IntVal(*da), IntVal(*db), dx);
  798. }
  799.  
  800. /*
  801.  *  iand(da, db) -> dx
  802.  */
  803.  
  804. int bigand(da, db, dx)
  805. dptr da, db, dx;
  806. {
  807.    struct b_bignum *a, *b, *x;
  808.    word alen, blen, xlen;
  809.    word i;
  810.    struct b_bignum *tad, *tbd;
  811.    DIGIT *ad, *bd;
  812.    struct descrip td;
  813.    char tdigits[INTBIGBLK];
  814.  
  815.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  816.       alen = LEN(LrgInt(da));
  817.       blen = LEN(LrgInt(db));
  818.       xlen = alen > blen ? alen : blen;
  819.       a = LrgInt(da);
  820.       b = LrgInt(db);
  821.       Protect(x = alcbignum(xlen), return Error);
  822.  
  823.       if (alen == xlen && !a->sign)
  824.          ad = DIG(a,0);
  825.       else {
  826.          Protect(tad = alcbignum(xlen), return Error);
  827.          ad = DIG(tad,0);
  828.          bdzero(ad, xlen - alen);
  829.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  830.          if (a->sign)
  831.         compl1(ad, ad, xlen);
  832.          }
  833.  
  834.       if (blen == xlen && !b->sign)
  835.          bd = DIG(b,0);
  836.       else {
  837.          Protect(tbd = alcbignum(xlen), return Error);
  838.          bd = DIG(tbd,0);
  839.          bdzero(bd, xlen - blen);
  840.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  841.          if (b->sign)
  842.         compl1(bd, bd, xlen);
  843.          }
  844.         
  845.       for (i = 0; i < xlen; i++)
  846.          *DIG(x,i) = ad[i] & bd[i];
  847.  
  848.       if (a->sign & b->sign) {
  849.          x->sign = 1;
  850.          compl1(DIG(x,0), DIG(x,0), xlen);
  851.          }
  852.       }
  853.    else if (Type(*da) == T_Lrgint) {   /* iand(bignum,integer) */
  854.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  855.       alen = LEN(LrgInt(da));
  856.       blen = LEN(LrgInt(&td));
  857.       xlen = alen > blen ? alen : blen;
  858.       a = LrgInt(da);
  859.       b = LrgInt(&td);
  860.       Protect(x = alcbignum(alen), return Error);
  861.  
  862.       if (alen == xlen && !a->sign)
  863.          ad = DIG(a,0);
  864.       else {
  865.          Protect(tad = alcbignum(xlen), return Error);
  866.          ad = DIG(tad,0);
  867.          bdzero(ad, xlen - alen);
  868.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  869.          if (a->sign)
  870.         compl1(ad, ad, xlen);
  871.          }
  872.  
  873.       if (blen == xlen && !b->sign)
  874.          bd = DIG(b,0);
  875.       else {
  876.          Protect(tbd = alcbignum(xlen), return Error);
  877.          bd = DIG(tbd,0);
  878.          bdzero(bd, xlen - blen);
  879.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  880.          if (b->sign)
  881.         compl1(bd, bd, xlen);
  882.          }
  883.         
  884.       for (i = 0; i < xlen; i++)
  885.          *DIG(x,i) = ad[i] & bd[i];
  886.  
  887.       if (a->sign & b->sign) {
  888.          x->sign = 1;
  889.          compl1(DIG(x,0), DIG(x,0), xlen);
  890.          }
  891.       }
  892.    else if (Type(*db) == T_Lrgint) {   /* iand(integer,bignum) */
  893.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  894.       alen = LEN(LrgInt(&td));
  895.       blen = LEN(LrgInt(db));
  896.       xlen = alen > blen ? alen : blen;
  897.       a = LrgInt(&td);
  898.       b = LrgInt(db);
  899.       Protect(x = alcbignum(blen), return Error);
  900.  
  901.       if (alen == xlen && !a->sign)
  902.          ad = DIG(a,0);
  903.       else {
  904.          Protect(tad = alcbignum(xlen), return Error);
  905.          ad = DIG(tad,0);
  906.          bdzero(ad, xlen - alen);
  907.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  908.          if (a->sign)
  909.         compl1(ad, ad, xlen);
  910.          }
  911.  
  912.       if (blen == xlen && !b->sign)
  913.          bd = DIG(b,0);
  914.       else {
  915.          Protect(tbd = alcbignum(xlen), return Error);
  916.          bd = DIG(tbd,0);
  917.          bdzero(bd, xlen - blen);
  918.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  919.          if (b->sign)
  920.         compl1(bd, bd, xlen);
  921.          }
  922.         
  923.       for (i = 0; i < xlen; i++)
  924.          *DIG(x,i) = ad[i] & bd[i];
  925.  
  926.       if (a->sign & b->sign) {
  927.          x->sign = 1;
  928.          compl1(DIG(x,0), DIG(x,0), xlen);
  929.          }
  930.       }
  931.    /* not called for iand(integer,integer) */
  932.  
  933.    return mkdesc(x, dx);
  934. }
  935.  
  936. /*
  937.  *  ior(da, db) -> dx
  938.  */
  939.  
  940. int bigor(da, db, dx)
  941. dptr da, db, dx;
  942. {
  943.    struct b_bignum *a, *b, *x;
  944.    word alen, blen, xlen;
  945.    word i;
  946.    struct b_bignum *tad, *tbd;
  947.    DIGIT *ad, *bd;
  948.    struct descrip td;
  949.    char tdigits[INTBIGBLK];
  950.  
  951.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  952.       alen = LEN(LrgInt(da));
  953.       blen = LEN(LrgInt(db));
  954.       xlen = alen > blen ? alen : blen;
  955.       a = LrgInt(da);
  956.       b = LrgInt(db);
  957.       Protect(x = alcbignum(xlen), return Error);
  958.  
  959.       if (alen == xlen && !a->sign)
  960.          ad = DIG(a,0);
  961.       else {
  962.          Protect(tad = alcbignum(xlen), return Error);
  963.          ad = DIG(tad,0);
  964.          bdzero(ad, xlen - alen);
  965.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  966.          if (a->sign)
  967.         compl1(ad, ad, xlen);
  968.          }
  969.  
  970.       if (blen == xlen && !b->sign)
  971.          bd = DIG(b,0);
  972.       else {
  973.          Protect(tbd = alcbignum(xlen), return Error);
  974.          bd = DIG(tbd,0);
  975.          bdzero(bd, xlen - blen);
  976.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  977.          if (b->sign)
  978.         compl1(bd, bd, xlen);
  979.          }
  980.         
  981.       for (i = 0; i < xlen; i++)
  982.          *DIG(x,i) = ad[i] | bd[i];
  983.  
  984.       if (a->sign | b->sign) {
  985.          x->sign = 1;
  986.          compl1(DIG(x,0), DIG(x,0), xlen);
  987.          }
  988.       }
  989.    else if (Type(*da) == T_Lrgint) {   /* ior(bignum,integer) */
  990.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  991.       alen = LEN(LrgInt(da));
  992.       blen = LEN(LrgInt(&td));
  993.       xlen = alen > blen ? alen : blen;
  994.       a = LrgInt(da);
  995.       b = LrgInt(&td);
  996.       Protect(x = alcbignum(alen), return Error);
  997.  
  998.       if (alen == xlen && !a->sign)
  999.          ad = DIG(a,0);
  1000.       else {
  1001.          Protect(tad = alcbignum(xlen), return Error);
  1002.          ad = DIG(tad,0);
  1003.          bdzero(ad, xlen - alen);
  1004.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1005.          if (a->sign)
  1006.         compl1(ad, ad, xlen);
  1007.          }
  1008.  
  1009.       if (blen == xlen && !b->sign)
  1010.          bd = DIG(b,0);
  1011.       else {
  1012.          Protect(tbd = alcbignum(xlen), return Error);
  1013.          bd = DIG(tbd,0);
  1014.          bdzero(bd, xlen - blen);
  1015.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1016.          if (b->sign)
  1017.         compl1(bd, bd, xlen);
  1018.          }
  1019.         
  1020.       for (i = 0; i < xlen; i++)
  1021.          *DIG(x,i) = ad[i] | bd[i];
  1022.  
  1023.       if (a->sign | b->sign) {
  1024.          x->sign = 1;
  1025.          compl1(DIG(x,0), DIG(x,0), xlen);
  1026.          }
  1027.       }
  1028.    else if (Type(*db) == T_Lrgint) {   /* ior(integer,bignym) */
  1029.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1030.       alen = LEN(LrgInt(&td));
  1031.       blen = LEN(LrgInt(db));
  1032.       xlen = alen > blen ? alen : blen;
  1033.       a = LrgInt(&td);
  1034.       b = LrgInt(db);
  1035.       Protect(x = alcbignum(blen), return Error);
  1036.  
  1037.       if (alen == xlen && !a->sign)
  1038.          ad = DIG(a,0);
  1039.       else {
  1040.          Protect(tad = alcbignum(xlen), return Error);
  1041.          ad = DIG(tad,0);
  1042.          bdzero(ad, xlen - alen);
  1043.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1044.          if (a->sign)
  1045.         compl1(ad, ad, xlen);
  1046.          }
  1047.  
  1048.       if (blen == xlen && !b->sign)
  1049.          bd = DIG(b,0);
  1050.       else {
  1051.          Protect(tbd = alcbignum(xlen), return Error);
  1052.          bd = DIG(tbd,0);
  1053.          bdzero(bd, xlen - blen);
  1054.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1055.          if (b->sign)
  1056.         compl1(bd, bd, xlen);
  1057.          }
  1058.         
  1059.       for (i = 0; i < xlen; i++)
  1060.          *DIG(x,i) = ad[i] | bd[i];
  1061.  
  1062.       if (a->sign | b->sign) {
  1063.          x->sign = 1;
  1064.          compl1(DIG(x,0), DIG(x,0), xlen);
  1065.          }
  1066.       }
  1067.    /* not called for ior(integer,integer) */
  1068.  
  1069.    return mkdesc(x, dx);
  1070. }
  1071.  
  1072. /*
  1073.  *  xor(da, db) -> dx
  1074.  */
  1075.  
  1076. int bigxor(da, db, dx)
  1077. dptr da, db, dx;
  1078. {
  1079.    struct b_bignum *a, *b, *x;
  1080.    word alen, blen, xlen;
  1081.    word i;
  1082.    struct b_bignum *tad, *tbd;
  1083.    DIGIT *ad, *bd;
  1084.    struct descrip td;
  1085.    char tdigits[INTBIGBLK];
  1086.  
  1087.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  1088.       alen = LEN(LrgInt(da));
  1089.       blen = LEN(LrgInt(db));
  1090.       xlen = alen > blen ? alen : blen;
  1091.       a = LrgInt(da);
  1092.       b = LrgInt(db);
  1093.       Protect(x = alcbignum(xlen), return Error);
  1094.  
  1095.       if (alen == xlen && !a->sign)
  1096.          ad = DIG(a,0);
  1097.       else {
  1098.          Protect(tad = alcbignum(xlen), return Error);
  1099.          ad = DIG(tad,0);
  1100.          bdzero(ad, xlen - alen);
  1101.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1102.          if (a->sign)
  1103.         compl1(ad, ad, xlen);
  1104.          }
  1105.  
  1106.       if (blen == xlen && !b->sign)
  1107.          bd = DIG(b,0);
  1108.       else {
  1109.          Protect(tbd = alcbignum(xlen), return Error);
  1110.          bd = DIG(tbd,0);
  1111.          bdzero(bd, xlen - blen);
  1112.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1113.          if (b->sign)
  1114.         compl1(bd, bd, xlen);
  1115.          }
  1116.  
  1117.       for (i = 0; i < xlen; i++)
  1118.          *DIG(x,i) = ad[i] ^ bd[i];
  1119.  
  1120.       if (a->sign ^ b->sign) {
  1121.          x->sign = 1;
  1122.          compl1(DIG(x,0), DIG(x,0), xlen);
  1123.          }
  1124.       }
  1125.    else if (Type(*da) == T_Lrgint) {   /* ixor(bignum,integer) */
  1126.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  1127.       alen = LEN(LrgInt(da));
  1128.       blen = LEN(LrgInt(&td));
  1129.       xlen = alen > blen ? alen : blen;
  1130.       a = LrgInt(da);
  1131.       b = LrgInt(&td);
  1132.       Protect(x = alcbignum(alen), return Error);
  1133.  
  1134.       if (alen == xlen && !a->sign)
  1135.          ad = DIG(a,0);
  1136.       else {
  1137.          Protect(tad = alcbignum(xlen), return Error);
  1138.          ad = DIG(tad,0);
  1139.          bdzero(ad, xlen - alen);
  1140.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1141.          if (a->sign)
  1142.         compl1(ad, ad, xlen);
  1143.          }
  1144.  
  1145.       if (blen == xlen && !b->sign)
  1146.          bd = DIG(b,0);
  1147.       else {
  1148.          Protect(tbd = alcbignum(xlen), return Error);
  1149.          bd = DIG(tbd,0);
  1150.          bdzero(bd, xlen - blen);
  1151.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1152.          if (b->sign)
  1153.         compl1(bd, bd, xlen);
  1154.          }
  1155.  
  1156.       for (i = 0; i < xlen; i++)
  1157.          *DIG(x,i) = ad[i] ^ bd[i];
  1158.  
  1159.       if (a->sign ^ b->sign) {
  1160.          x->sign = 1;
  1161.          compl1(DIG(x,0), DIG(x,0), xlen);
  1162.          }
  1163.       }
  1164.    else if (Type(*db) == T_Lrgint) {   /* ixor(integer,bignum) */
  1165.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1166.       alen = LEN(LrgInt(&td));
  1167.       blen = LEN(LrgInt(db));
  1168.       xlen = alen > blen ? alen : blen;
  1169.       a = LrgInt(&td);
  1170.       b = LrgInt(db);
  1171.       Protect(x = alcbignum(blen), return Error);
  1172.  
  1173.       if (alen == xlen && !a->sign)
  1174.          ad = DIG(a,0);
  1175.       else {
  1176.          Protect(tad = alcbignum(xlen), return Error);
  1177.          ad = DIG(tad,0);
  1178.          bdzero(ad, xlen - alen);
  1179.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1180.          if (a->sign)
  1181.         compl1(ad, ad, xlen);
  1182.          }
  1183.  
  1184.       if (blen == xlen && !b->sign)
  1185.          bd = DIG(b,0);
  1186.       else {
  1187.          Protect(tbd = alcbignum(xlen), return Error);
  1188.          bd = DIG(tbd,0);
  1189.          bdzero(bd, xlen - blen);
  1190.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1191.          if (b->sign)
  1192.         compl1(bd, bd, xlen);
  1193.          }
  1194.  
  1195.       for (i = 0; i < xlen; i++)
  1196.          *DIG(x,i) = ad[i] ^ bd[i];
  1197.  
  1198.       if (a->sign ^ b->sign) {
  1199.          x->sign = 1;
  1200.          compl1(DIG(x,0), DIG(x,0), xlen);
  1201.          }
  1202.       }
  1203.    /* not called for ixor(integer,integer) */
  1204.  
  1205.    return mkdesc(x, dx);
  1206. }
  1207.  
  1208. /*
  1209.  *  bigshift(da, db) -> dx
  1210.  */
  1211.  
  1212. int bigshift(da, db, dx)
  1213. dptr da, db, dx;
  1214. {
  1215.    struct b_bignum *a, *x;
  1216.    word alen;
  1217.    word r = IntVal(*db) % NB;
  1218.    word q = (r >= 0 ? IntVal(*db) : (IntVal(*db) - (r += NB))) / NB;
  1219.    word xlen;
  1220.    DIGIT *ad;
  1221.    struct b_bignum *tad;
  1222.    struct descrip td;
  1223.    char tdigits[INTBIGBLK];
  1224.  
  1225.    if (Type(*da) == T_Integer) {
  1226.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1227.       da = &td;
  1228.       }
  1229.  
  1230.    alen = LEN(LrgInt(da));
  1231.    xlen = alen + q + 1;
  1232.    if (xlen <= 0) {
  1233.       MakeInt(0, dx);
  1234.       return Succeeded;
  1235.       }
  1236.    else {
  1237.       a = LrgInt(da);
  1238.       Protect(x = alcbignum(xlen), return Error);
  1239.  
  1240.       if (a->sign && IntVal(*db) > (word)0) {
  1241.          Protect(tad = alcbignum(alen), return Error);
  1242.          ad = DIG(tad,0);
  1243.          bdcopy(DIG(a,0), ad, alen);
  1244.          compl1(ad, ad, alen);
  1245.          }
  1246.       else
  1247.          ad = DIG(a,0);
  1248.  
  1249.       if (q >= 0) {
  1250.          *DIG(x,0) = shifti1(ad, r, (DIGIT)0, DIG(x,1), alen);
  1251.          bdzero(DIG(x,alen+1), q);
  1252.          }
  1253.       else
  1254.          *DIG(x,0) = shifti1(ad, r, ad[alen+q] >> (NB-r), DIG(x,1), alen+q);
  1255.  
  1256.       if (a->sign && IntVal(*db) > (word)0) {
  1257.          x->sign = 1;
  1258.          *DIG(x,0) |= B - (1 << r);
  1259.          compl1(DIG(x,0), DIG(x,0), xlen);
  1260.          }
  1261.       return mkdesc(x, dx);
  1262.       }
  1263.    }
  1264.  
  1265. /*
  1266.  *  negative if da < db
  1267.  *  zero if da == db
  1268.  *  positive if da > db
  1269.  */
  1270.  
  1271. word bigcmp(da, db)
  1272. dptr da, db;
  1273. {
  1274.    struct b_bignum *a = LrgInt(da);
  1275.    struct b_bignum *b = LrgInt(db);
  1276.    word alen, blen; 
  1277.  
  1278.    if (Type(*da) == T_Lrgint && Type(*db) == T_Lrgint) {
  1279.       if (a->sign != b->sign)
  1280.          return (b->sign - a->sign);
  1281.       alen = LEN(a);
  1282.       blen = LEN(b);
  1283.       if (alen != blen)
  1284.          return (a->sign ? blen - alen : alen - blen);
  1285.  
  1286.       if (a->sign)
  1287.          return cmp1(DIG(b,0), DIG(a,0), alen);
  1288.       else
  1289.          return cmp1(DIG(a,0), DIG(b,0), alen);
  1290.       }
  1291.    else if (Type(*da) == T_Lrgint)    /* cmp(bignum, integer) */
  1292.       return bigcmpi(da, IntVal(*db));
  1293.    else                               /* cmp(integer, bignum) */
  1294.       return -bigcmpi(db, IntVal(*da));
  1295. }
  1296.  
  1297. /*
  1298.  *  ?da -> dx
  1299.  */  
  1300.  
  1301. int bigrand(da, dx)
  1302. dptr da, dx;
  1303. {
  1304.    struct b_bignum *a;
  1305.    word alen = LEN(LrgInt(da));
  1306.    struct b_bignum *x;
  1307.    struct b_bignum *td;
  1308.    DIGIT *d;
  1309.    word i;
  1310.    double rval;
  1311.  
  1312.    Protect(x = alcbignum(alen), return Error);
  1313.    Protect(td = alcbignum(alen + 1), return Error);
  1314.    d = DIG(td,0);
  1315.    a = LrgInt(da);
  1316.  
  1317.    for (i = alen; i >= 0; i--) {
  1318.       rval = RandVal;
  1319.       d[i] = rval * B;
  1320.       }
  1321.     
  1322.    if (div1(d, DIG(a,0), NULL, DIG(x,0), (word)1, alen) == Error)
  1323.       return Error;
  1324.    addi1(DIG(x,0), (word)1, DIG(x,0), alen);
  1325.    return mkdesc(x, dx);
  1326. }
  1327.  
  1328. /*
  1329.  *  da + i -> dx
  1330.  */
  1331.  
  1332. static int bigaddi(da, i, dx)
  1333. dptr da, dx;
  1334. word i;
  1335. {
  1336.    struct b_bignum *a, *x; 
  1337.    word alen; 
  1338.  
  1339.    if (i < 0 && i > MinLong)
  1340.       return bigsubi(da, -i, dx);
  1341.    else if (i != (DIGIT)i) {
  1342.       struct descrip td;
  1343.       char tdigits[INTBIGBLK];
  1344.  
  1345.       itobig(i, (struct b_bignum *)tdigits, &td);
  1346.       return bigadd(da, &td, dx);
  1347.       }
  1348.    else {
  1349.       alen = LEN(LrgInt(da));
  1350.       a = LrgInt(da);
  1351.       if (a->sign) {
  1352.      Protect(x = alcbignum(alen), return Error);
  1353.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1354.          }
  1355.       else {
  1356.          Protect(x = alcbignum(alen + 1), return Error);
  1357.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1358.          }
  1359.       x->sign = a->sign;
  1360.       return mkdesc(x, dx);
  1361.       }
  1362. }
  1363.  
  1364. /*
  1365.  *  da - i -> dx
  1366.  */
  1367.  
  1368. static int bigsubi(da, i, dx)
  1369. dptr da, dx;
  1370. word i;
  1371. {
  1372.    struct b_bignum *a, *x; 
  1373.    word alen;
  1374.  
  1375.    if (i < 0 && i > MinLong)
  1376.       return bigaddi(da, -i, dx);
  1377.    else if (i != (DIGIT)i) {
  1378.       struct descrip td;
  1379.       char tdigits[INTBIGBLK];
  1380.  
  1381.       itobig(i, (struct b_bignum *)tdigits, &td);
  1382.       return bigsub(da, &td, dx);
  1383.       }
  1384.    else {
  1385.       alen = LEN(LrgInt(da));
  1386.       a = LrgInt(da);
  1387.       if (a->sign) {
  1388.          Protect(x = alcbignum(alen + 1), return Error);
  1389.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1390.          }
  1391.       else {
  1392.          Protect(x = alcbignum(alen), return Error);
  1393.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1394.          }
  1395.       x->sign = a->sign;
  1396.       return mkdesc(x, dx);
  1397.       }
  1398. }
  1399.  
  1400. /*
  1401.  *  da * i -> dx
  1402.  */
  1403.  
  1404. static int bigmuli(da, i, dx)
  1405. dptr da, dx;
  1406. word i;
  1407. {
  1408.    struct b_bignum *a, *x; 
  1409.    word alen;
  1410.  
  1411.    if (i <= -B || i >= B) {
  1412.       struct descrip td;
  1413.       char tdigits[INTBIGBLK];
  1414.  
  1415.       itobig(i, (struct b_bignum *)tdigits, &td);
  1416.       return bigmul(da, &td, dx);
  1417.       }
  1418.    else {
  1419.       alen = LEN(LrgInt(da));
  1420.       a = LrgInt(da);
  1421.       Protect(x = alcbignum(alen + 1), return Error);
  1422.       if (i >= 0)
  1423.          x->sign = a->sign;
  1424.       else {
  1425.          x->sign = 1 ^ a->sign;
  1426.          i = -i;
  1427.          }
  1428.       *DIG(x,0) = muli1(DIG(a,0), i, 0, DIG(x,1), alen);
  1429.       return mkdesc(x, dx);
  1430.       }
  1431. }
  1432.  
  1433. /*
  1434.  *  da / i -> dx
  1435.  */
  1436.  
  1437. static int bigdivi(da, i, dx)
  1438. dptr da, dx;
  1439. word i;
  1440. {
  1441.    struct b_bignum *a, *x; 
  1442.    word alen;
  1443.  
  1444.    if (i <= -B || i >= B) {
  1445.       struct descrip td;
  1446.       char tdigits[INTBIGBLK];
  1447.  
  1448.       itobig(i, (struct b_bignum *)tdigits, &td);
  1449.       return bigdiv(da, &td, dx);
  1450.       }
  1451.    else {
  1452.       alen = LEN(LrgInt(da));
  1453.       a = LrgInt(da);
  1454.       Protect(x = alcbignum(alen), return Error);
  1455.       if (i >= 0)
  1456.          x->sign = a->sign;
  1457.       else {
  1458.          x->sign = 1 ^ a->sign;
  1459.          i = -i;
  1460.          }
  1461.       divi1(DIG(a,0), i, DIG(x,0), alen);
  1462.       return mkdesc(x, dx);
  1463.       }
  1464. }
  1465.  
  1466. /*
  1467.  *  da % i -> dx
  1468.  */
  1469.  
  1470. static int bigmodi(da, i, dx)
  1471. dptr da, dx;
  1472. word i;
  1473. {
  1474.    struct b_bignum *a, *temp;
  1475.    word alen;
  1476.    word x;
  1477.  
  1478.    if (i <= -B || i >= B) {
  1479.       struct descrip td;
  1480.       char tdigits[INTBIGBLK];
  1481.  
  1482.       itobig(i, (struct b_bignum *)tdigits, &td);
  1483.       return bigmod(da, &td, dx);
  1484.       }
  1485.    else {
  1486.       alen = LEN(LrgInt(da));
  1487.       a = LrgInt(da);
  1488.       Protect(temp = alcbignum(alen), return Error);
  1489.       x = divi1(DIG(a,0), Abs(i), DIG(temp,0), alen);
  1490.       if (a->sign)
  1491.      x = -x;
  1492.       MakeInt(x, dx);
  1493.       return Succeeded;
  1494.       }
  1495. }
  1496.  
  1497. /*
  1498.  *  da ^ i -> dx
  1499.  */
  1500.  
  1501. static int bigpowi(da, i, dx)
  1502. dptr da, dx;
  1503. word i;
  1504. {
  1505.    int n = WordBits;
  1506.    
  1507.    if (i > 0) {
  1508.       /* scan bits left to right.  skip leading 1. */
  1509.       while (--n >= 0)
  1510.          if (i & ((word)1 << n))
  1511.         break;
  1512.       /* then, for each zero, square the partial result;
  1513.          for each one, square it and multiply it by a */
  1514.       *dx = *da;
  1515.       while (--n >= 0) {
  1516.          if (bigmul(dx, dx, dx) == Error)
  1517.         return Error;
  1518.          if (i & ((word)1 << n))
  1519.             if (bigmul(dx, da, dx) == Error)
  1520.            return Error;
  1521.          }
  1522.       }
  1523.    else if (i == 0) {
  1524.       MakeInt(1, dx);
  1525.       }
  1526.    else {
  1527.       MakeInt(0, dx);
  1528.       }
  1529.    return Succeeded;
  1530. }
  1531.  
  1532. /*
  1533.  *  a ^ i -> dx
  1534.  */
  1535.  
  1536. static int bigpowii(a, i, dx)
  1537. word a, i;
  1538. dptr dx;
  1539. {
  1540.    word x, y;
  1541.    int n = WordBits;
  1542.    int isbig = 0;
  1543.  
  1544.    if (a == 0 || i <= 0) {              /* special cases */
  1545.       if (a == 0 && i <= 0)             /* 0 ^ negative -> error */
  1546.          ReturnErrNum(204,Error);
  1547.       if (i == 0) {
  1548.          MakeInt(1, dx);
  1549.          return Succeeded;
  1550.          }
  1551.       if (a == -1) {                    /* -1 ^ [odd,even] -> [-1,+1] */
  1552.          if (!(i & 1))
  1553.         a = 1;
  1554.          }
  1555.       else if (a != 1) {                /* 1 ^ any -> 1 */
  1556.          a = 0;
  1557.          }                   /* others ^ negative -> 0 */
  1558.       MakeInt(a, dx);
  1559.       }
  1560.    else {
  1561.       struct descrip td;
  1562.       char tdigits[INTBIGBLK];
  1563.  
  1564.       /* scan bits left to right.  skip leading 1. */
  1565.       while (--n >= 0)
  1566.          if (i & ((word)1 << n))
  1567.         break;
  1568.       /* then, for each zero, square the partial result;
  1569.          for each one, square it and multiply it by a */
  1570.       x = a;
  1571.       while (--n >= 0) {
  1572.          if (isbig) {
  1573.             if (bigmul(dx, dx, dx) == Error)
  1574.            return Error;
  1575.         }
  1576.          else {
  1577.             y = mul(x, x);
  1578.             if (!over_flow)
  1579.                x = y;
  1580.             else {
  1581.                itobig(x, (struct b_bignum *)tdigits, &td);
  1582.                if (bigmul(&td, &td, dx) == Error)
  1583.                  return Error;
  1584.                isbig = (Type(*dx) == T_Lrgint);
  1585.                } 
  1586.             }
  1587.          if (i & ((word)1 << n)) {
  1588.             if (isbig) {
  1589.                if (bigmuli(dx, a, dx) == Error)
  1590.           return Error;
  1591.            }
  1592.             else {
  1593.                y = mul(x, a);
  1594.                if (!over_flow)
  1595.                   x = y;
  1596.                else {
  1597.                   itobig(x, (struct b_bignum *)tdigits, &td);
  1598.                   if (bigmuli(&td, a, dx) == Error)
  1599.              return Error;
  1600.                   isbig = (Type(*dx) == T_Lrgint);
  1601.                   }
  1602.                }
  1603.             }
  1604.          }
  1605.       if (!isbig) {
  1606.      MakeInt(x, dx);
  1607.      }
  1608.       }
  1609.    return Succeeded;
  1610. }
  1611.  
  1612. /*
  1613.  *  negative if da < i
  1614.  *  zero if da == i
  1615.  *  positive if da > i
  1616.  */  
  1617.   
  1618. static word bigcmpi(da, i)
  1619. dptr da;
  1620. word i;
  1621. {
  1622.    struct b_bignum *a = LrgInt(da);
  1623.    word alen = LEN(a);
  1624.  
  1625.    if (i > -B && i < B) {
  1626.       if (i >= 0)
  1627.          if (a->sign)
  1628.         return -1;
  1629.          else
  1630.         return cmpi1(DIG(a,0), i, alen);
  1631.       else
  1632.          if (a->sign)
  1633.         return -cmpi1(DIG(a,0), -i, alen);
  1634.          else
  1635.         return 1;
  1636.       }
  1637.    else {
  1638.       struct descrip td;
  1639.       char tdigits[INTBIGBLK];
  1640.  
  1641.       itobig(i, (struct b_bignum *)tdigits, &td);
  1642.       return bigcmp(da, &td);
  1643.       }
  1644. }
  1645.  
  1646.  
  1647. /* These are all straight out of Knuth vol. 2, Sec. 4.3.1. */
  1648.  
  1649. /*
  1650.  *  (u,n) + (v,n) -> (w,n)
  1651.  *
  1652.  *  returns carry, 0 or 1
  1653.  */
  1654.  
  1655. static DIGIT add1(u, v, w, n)
  1656. DIGIT *u, *v, *w;
  1657. word n;
  1658. {
  1659.    uword dig, carry; 
  1660.    word i;
  1661.  
  1662.    carry = 0;
  1663.    for (i = n; --i >= 0; ) {
  1664.       dig = (uword)u[i] + v[i] + carry;
  1665.       w[i] = lo(dig);
  1666.       carry = hi(dig);
  1667.       }
  1668.    return carry;
  1669. }
  1670.  
  1671. /*
  1672.  *  (u,n) - (v,n) -> (w,n)
  1673.  *
  1674.  *  returns carry, 0 or -1
  1675.  */
  1676.  
  1677. static word sub1(u, v, w, n)
  1678. DIGIT *u, *v, *w;
  1679. word n;
  1680. {
  1681.    uword dig, carry; 
  1682.    word i;
  1683.  
  1684.    carry = 0;
  1685.    for (i = n; --i >= 0; ) {
  1686.       dig = (uword)u[i] - v[i] + carry;
  1687.       w[i] = lo(dig);
  1688.       carry = signed_hi(dig);
  1689.       }
  1690.    return carry;
  1691. }
  1692.  
  1693. /*
  1694.  *  (u,n) * (v,m) -> (w,m+n)
  1695.  */
  1696.  
  1697. static novalue mul1(u, v, w, n, m)
  1698. DIGIT *u, *v, *w;
  1699. word n, m;
  1700. {
  1701.    word i, j;
  1702.    uword dig, carry;
  1703.  
  1704.    bdzero(&w[m], n);
  1705.  
  1706.    for (j = m; --j >= 0; ) {
  1707.       carry = 0;
  1708.       for (i = n; --i >= 0; ) {
  1709.          dig = (uword)u[i] * v[j] + w[i+j+1] + carry;
  1710.          w[i+j+1] = lo(dig);
  1711.          carry = hi(dig);
  1712.          }
  1713.       w[j] = carry;
  1714.       }
  1715. }
  1716.  
  1717. /*
  1718.  *  (a,m+n) / (b,n) -> (q,m+1) (r,n)
  1719.  *
  1720.  *  if q or r is NULL, the quotient or remainder is discarded
  1721.  */
  1722.  
  1723. static int div1(a, b, q, r, m, n)
  1724. DIGIT *a, *b, *q, *r;
  1725. word m, n;
  1726. {
  1727.    uword qhat, rhat;
  1728.    uword dig, carry;
  1729.    struct b_bignum *tu, *tv;
  1730.    DIGIT *u, *v;
  1731.    word d;
  1732.    word i, j;
  1733.  
  1734.    Protect(tu = alcbignum(m + n + 1), return Error);
  1735.    Protect(tv = alcbignum(n), return Error);
  1736.    u = DIG(tu,0);
  1737.    v = DIG(tv,0);
  1738.  
  1739.    /* D1 */
  1740.    for (d = 0; d < NB; d++)
  1741.       if (b[0] & (1 << (NB - 1 - d)))
  1742.          break;
  1743.  
  1744.    u[0] = shifti1(a, d, (DIGIT)0, &u[1], m+n);
  1745.    shifti1(b, d, (DIGIT)0, v, n);
  1746.  
  1747.    /* D2, D7 */
  1748.    for (j = 0; j <= m; j++) {
  1749.       /* D3 */
  1750.       if (u[j] == v[0]) {
  1751.          qhat = B - 1;
  1752.          rhat = (uword)v[0] + u[j+1];
  1753.          }
  1754.       else {
  1755.          uword numerator = dbl(u[j], u[j+1]);
  1756.          qhat = numerator / (uword)v[0];
  1757.          rhat = numerator % (uword)v[0];
  1758.          }
  1759.  
  1760.       while (rhat < B && qhat * v[1] > dbl(rhat, u[j+2])) {
  1761.          qhat -= 1;
  1762.          rhat += v[0];
  1763.          }
  1764.             
  1765.       /* D4 */
  1766.       carry = 0;
  1767.       for (i = n; i > 0; i--) {
  1768.          dig = u[i+j] - v[i-1] * qhat + carry;       /* -BSQ+B .. B-1 */
  1769.          u[i+j] = lo(dig);
  1770.          if ((uword)dig < B)
  1771.             carry = hi(dig);
  1772.          else carry = hi(dig) | -B;
  1773.          }
  1774.       carry = (word)(carry + u[j]) < 0;
  1775.  
  1776.       /* D5 */
  1777.       if (q)
  1778.      q[j] = qhat;
  1779.  
  1780.       /* D6 */
  1781.       if (carry) {
  1782.          if (q)
  1783.         q[j] -= 1;
  1784.          carry = 0;
  1785.          for (i = n; i > 0; i--) {
  1786.             dig = (uword)u[i+j] + v[i-1] + carry;
  1787.             u[i+j] = lo(dig);
  1788.             carry = hi(dig);
  1789.             }
  1790.          }
  1791.       }
  1792.  
  1793.    if (r) {
  1794.       if (d == 0)
  1795.          shifti1(&u[m+1], (word)d, (DIGIT)0, r, n);
  1796.       else
  1797.          r[0] = shifti1(&u[m+1], (word)(NB - d), u[m+n]>>d, &r[1], n - 1);
  1798.       }
  1799.    return Succeeded;
  1800. }
  1801.  
  1802. /*
  1803.  *  - (u,n) -> (w,n)
  1804.  *
  1805.  */
  1806.  
  1807. static novalue compl1(u, w, n)
  1808. DIGIT *u, *w;
  1809. word n;
  1810. {
  1811.    uword dig, carry = 0;
  1812.    word i;
  1813.  
  1814.    for (i = n; --i >= 0; ) {
  1815.       dig = carry - u[i];
  1816.       w[i] = lo(dig);
  1817.       carry = signed_hi(dig);
  1818.       }
  1819. }
  1820.  
  1821. /*
  1822.  *  (u,n) : (v,n)
  1823.  */
  1824.  
  1825. static word cmp1(u, v, n)
  1826. DIGIT *u, *v;
  1827. word n;
  1828. {
  1829.    word i;
  1830.  
  1831.    for (i = 0; i < n; i++)
  1832.       if (u[i] != v[i])
  1833.          return u[i] > v[i] ? 1 : -1;
  1834.    return 0;
  1835. }
  1836.  
  1837. /*
  1838.  *  (u,n) + k -> (w,n)
  1839.  *
  1840.  *  k in 0 .. B-1
  1841.  *  returns carry, 0 or 1
  1842.  */
  1843.  
  1844. static DIGIT addi1(u, k, w, n)
  1845. DIGIT *u, *w;
  1846. word k;
  1847. word n;
  1848. {
  1849.    uword dig, carry;
  1850.    word i;
  1851.     
  1852.    carry = k;
  1853.    for (i = n; --i >= 0; ) {
  1854.       dig = (uword)u[i] + carry;
  1855.       w[i] = lo(dig);
  1856.       carry = hi(dig);
  1857.       }
  1858.    return carry;
  1859. }
  1860.  
  1861. /*
  1862.  *  (u,n) - k -> (w,n)
  1863.  *
  1864.  *  k in 0 .. B-1
  1865.  *  u must be greater than k
  1866.  */
  1867.  
  1868. static novalue subi1(u, k, w, n)
  1869. DIGIT *u, *w;
  1870. word k;
  1871. word n;
  1872. {
  1873.    uword dig, carry;
  1874.    word i;
  1875.     
  1876.    carry = -k;
  1877.    for (i = n; --i >= 0; ) {
  1878.       dig = (uword)u[i] + carry;
  1879.       w[i] = lo(dig);
  1880.       carry = signed_hi(dig);
  1881.       }
  1882. }
  1883.  
  1884. /*
  1885.  *  (u,n) * k + c -> (w,n)
  1886.  *
  1887.  *  k in 0 .. B-1
  1888.  *  returns carry, 0 .. B-1
  1889.  */
  1890.  
  1891. static DIGIT muli1(u, k, c, w, n)
  1892. DIGIT *u, *w;
  1893. word k;
  1894. int c;
  1895. word n;
  1896. {
  1897.    uword dig, carry;
  1898.    word i;
  1899.  
  1900.    carry = c;
  1901.    for (i = n; --i >= 0; ) {
  1902.       dig = (uword)k * u[i] + carry;
  1903.       w[i] = lo(dig);
  1904.       carry = hi(dig);
  1905.       }
  1906.    return carry;
  1907. }
  1908.  
  1909. /*
  1910.  *  (u,n) / k -> (w,n)
  1911.  *
  1912.  *  k in 0 .. B-1
  1913.  *  returns remainder, 0 .. B-1
  1914.  */
  1915.  
  1916. static DIGIT divi1(u, k, w, n)
  1917. DIGIT *u, *w;
  1918. word k;
  1919. word n;
  1920. {
  1921.    uword dig, remain;
  1922.    word i;
  1923.  
  1924.    remain = 0;
  1925.    for (i = 0; i < n; i++) {
  1926.       dig = dbl(remain, u[i]);
  1927.       w[i] = dig / k;
  1928.       remain = dig % k;
  1929.       }
  1930.    return remain;
  1931. }
  1932.  
  1933. /*
  1934.  *  ((u,n) << k) + c -> (w,n)
  1935.  *
  1936.  *  k in 0 .. NB-1
  1937.  *  c in 0 .. B-1 
  1938.  *  returns carry, 0 .. B-1
  1939.  */
  1940.  
  1941. static DIGIT shifti1(u, k, c, w, n)
  1942. DIGIT *u, c, *w;
  1943. word k;
  1944. word n;
  1945. {
  1946.    uword dig;
  1947.    word i;
  1948.  
  1949.    if (k == 0) {
  1950.       bdcopy(u, w, n);
  1951.       return 0;
  1952.       }
  1953.     
  1954.    for (i = n; --i >= 0; ) {
  1955.       dig = ((uword)u[i] << k) + c;
  1956.       w[i] = lo(dig);
  1957.       c = hi(dig);
  1958.       }
  1959.    return c;
  1960. }
  1961.  
  1962. /*
  1963.  *  (u,n) : k
  1964.  *
  1965.  *  k in 0 .. B-1
  1966.  */
  1967.  
  1968. static word cmpi1(u, k, n)
  1969. DIGIT *u;
  1970. word k;
  1971. word n;
  1972. {
  1973.    word i;
  1974.  
  1975.    for (i = 0; i < n-1; i++)
  1976.       if (u[i])
  1977.      return 1;
  1978.    if (u[n - 1] == (DIGIT)k)
  1979.       return 0;
  1980.    return u[n - 1] > (DIGIT)k ? 1 : -1;
  1981. }
  1982.  
  1983. #ifndef SysMem
  1984. static novalue bdzero(dest, l)
  1985. DIGIT *dest;
  1986. word l;
  1987. {
  1988.    word i;
  1989.  
  1990.    for (i = 0; i < l; i++)
  1991.       dest[i] = 0;
  1992. }
  1993.  
  1994. static novalue bdcopy(src, dest, l)
  1995. DIGIT *src, *dest;
  1996. word l;
  1997. {
  1998.    word i;
  1999.  
  2000.    for (i = 0; i < l; i++)
  2001.       dest[i] = src[i];
  2002. }
  2003. #endif                    /* SysMem */
  2004. #else                    /* LargeInts */
  2005. static char x;            /* prevent empty module */
  2006. #endif                    /* LargeInts */
  2007.